The task of multiplying a variable by a loadable constant is required by a large number of computer applications. Two such applications, among others, are digital signal processing and the implementation of a neural network. In both cases, the application is characterized by a high number of multiplications of a variable by a constant. Whether the variable is received from neural nodes or is a time sampled signal, the same type of mathematical operation is required. The present invention is a technique for carrying out the basic task of multiplying a variable by a constant for these types of applications. This technique and its advantages are applicable to any computer operation requiring a multiplication operation. The technique is especially applicable to digital filters and neural networks because of the large number of repetitive multiplication operations that take place in those applications. The technique described below is described in the context of a digital filter for illustrative purposes even though it is understood that the technique is applicable to other computer applications.
Digital filtering is a technique for analyzing and modifying an analog signal. This technique is implemented by a multi-stage apparatus in which the jth stage generates a product produced by multiplying the instantaneous value of a filter input X(t) and a filter stage coefficient Cj. For example, a digital finite impulse response (FIR) filter is represented by: ##EQU1## Equation (1) represents a FIR filter with constant coefficients. The apparatus which implements the filter of equation (1) consists of a number of stages. At each stage, the ith coefficient Ci is multiplied by the magnitude of the input signal X(t) to produce a product. Y(t) is obtained by taking the sum of all the J+1 stage products. A conventional architecture for the FIR filter of equation (1) is represented by the apparatus of FIG. 1. In FIG. 1, X(t) is multiplied by coefficient Cj in multiplier 10 and the product Yj is stored in register Rj. The product Yj is added to the product of C(j-1) and X(t) in adder 15, and stored as intermediate result Y(j-1). The intermediate results are then added and stored to successive products of Ci (i=j to 0) and X(t) until i=0. Y(t) is the sum of the intermediate results and Ci multiplied by X(t).
The effectiveness of the digital filter depends on the speed with which Y(t) can be computed. The sampled and modified signal Y(t) should be as close to the corresponding X(t) in time as possible. If calculating Y(t) is slow, then the number of stages is reduced so that Y(t) can be computed faster, and as a result, X(t) more nearly corresponds to Y(t) in the time domain. However, reducing the number of stages, reduces the accuracy in modifying X(t). That is, there are fewer stages and therefore less accuracy in determining the magnitude of Y(t). Therefore, making the calculation of Y(t) faster, increases the accuracy of the output because more stages can be included for the same amount of processing time.
A significant factor in the speed with which Y(t) is determined is the speed of the multiplier in the digital filter. A high speed binary multiplier accepts any two operands and generates the product of the operands. Typically, these multipliers are much slower than adders because they shift and add for each bit of Ci and this generally requires several clock cycles of the computer to complete a single multiplication function. Even the use of special algorithms to reduce the number of bits being shifted and added, such as Booths Algorithm, do not make such multipliers fast enough for many digital filter applications in which speed and accuracy are required.
A solution to this problem has been to replace the general multiplier with a Look Up Table (LUT) which provides the function of the multiplier in the digital filter environment. The LUT has stored all the possible products of X(t) and a single coefficient Cj. This is possible because X(t) is represented by a finite number of bits which means there can only be a finite number of values for X(t). The product of each of the finite number of values and Cj are arranged in the LUT such that the value of X(t) is the address in the LUT of the product of X(t) and Cj. There is a LUT for each Ci (i=0 to j), just as there would be a multiplier for each stage of the digital filter. When X(t) addresses the various LUTs, the corresponding products are output to the adders 15 of the digital filter. The use of the LUT is much faster than the multiplier because an address and retrieve operation is faster than multiple shift and add operations. This results in a faster digital filter. The use of the LUT is practical in a digital filter because Cj is constant (or changes infrequently) and therefore the products are just reused and only have to be generated once (or infrequently). The problem with this solution to the speed problem of the digital filter is that LUTs are much larger than multipliers. The multiplication of an N bit X(t) by an M bit Cj, results in an (N+M) bit product Since there are 2.sup.N possibilities for X(t), this results in 2.sup.N .times.(N+M) bits of storage necessary for each LUT. A typical 8.times.8 bit multiplication requires 4,096 bits of storage for one LUT. Such storage requirements are very expensive compared to the remaining circuitry which makes up the rest of the digital filter.